package Leetcode;

import java.util.Stack;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class trap {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]){
                int mid = stack.pop();
                if (!stack.isEmpty()){
                    int h = Math.min(height[stack.peek()], height[i]) - height[mid];
                    int w = i - stack.peek() - 1;
                    result += h * w;
                }
            }
            stack.push(i);
        }
        return result;
    }
}
